package daily;

public class ReverseLink {

    public static void main(String[] args) {
        ReverseLink reverseLink = new ReverseLink();
        ListNode head = reverseLink.createList(new int[]{2, 3, 4, 5, 5, 6, 7, 7, 8});
        reverseLink.printList(head);
        ListNode newHead = reverseLink.reverse(head);
        reverseLink.printList(newHead);
    }


    /**
     * 将链表逆序
     *
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode node = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return node;

    }


    /**
     * 创建链表
     * 从数组生成链表
     *
     * @param values 数组中的每个元素对应链表的节点值
     * @return 链表头节点
     */
    public ListNode createList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    /**
     * 打印链表
     * 遍历链表并打印每个节点的值
     *
     * @param head 链表的头节点
     */
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.next;
        }
        System.out.println();
    }


    public static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }
}
